题目分析

这道题目是一个博弈问题，因为很难去遍历所有的情况，我们只能通过上一步对手的情况，选择我们相应的行为，因此博弈问题一般可以通过动态规划求解。

状态转移方程的求解

题目中说每次选取一个满足条件的数，进行减法替换。所以以可以构建一个从0到N的数组，保存到达这N个数字的胜负情况，博弈的题目要求是两个人都是最优策略，因此我们可以推断出，当判断第N个数时，如果从1到N的所有满足条件的数字有一个会导致败局时，那么第N个数就是必胜局，当从1到N的所有满足条件的数字全都是胜局时，那么第N个数就是必败局。因为爱丽丝先手，0到N中如果有一个数字K会导致必败局，那么爱丽丝就选择K，这样，鲍勃就会走入必败的局面，因此爱丽丝必胜，如果0到N的所有数字都是必胜局，那么爱丽丝无论如何选择，鲍勃都会到达必胜局，因此爱丽丝必败。

DP

根据状态转移方程，我们可以轻易的求得该题，x从2遍历到N，对于每一个数x，计算出所有符合条件的数，因为要满足整除条件，因此符合条件的数从1遍历到x的平方根即可。所以时间复杂度为$O(n\sqrt{n})$，空间复杂度为$O(n)$。

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = [False] * (N + 1)

        for i in range(2, N + 1):
            for x in range(1, int(i ** 0.5) + 1):
                if i % x == 0:
                    if not dp[i - x]:
                        dp[i] = True
                        break
        return dp[-1]

归纳法

归纳法是最简单的方法，但不是我首推的方法，因为归纳法不能解决大多数问题，所以说并不是这个问题的通解。
我们已知1为必败态，因为找不到满足条件的数。
我们已知2为必胜态，因为我们可以找到因数1满足条件，而且1为必败态，因此爱丽丝选择1，就会让鲍勃陷入必败态。
我们尝试3，因为1是满足条件的唯一解，而且2为必胜态，所以3为必败态。
我们尝试4，因为3是必败态，所以爱丽丝会选择1，让鲍勃陷入必败态，爱丽丝是必胜态。
我们尝试5，因为1是满足条件的唯一解，而且4为必胜态，所以5为必败态。
……我们会发现，1，3，5，…是必败态，2，4，…是必胜态。所以我们猜测奇数态都是必败态，偶数态都是必胜态。
我们假设k为偶数，并且小于等于k的数都满足条件，奇数为必败态，偶数为必胜态。那么当爱丽丝处于k+1奇数时，由于奇数的因子必定为奇数，所以爱丽丝只能选择奇数。这样鲍勃会处于一个小于等于k的偶数，由假定可知偶数是必胜态，那么鲍勃必胜，爱丽丝必败，满足条件。
我们假设k为奇数，并且小于等于k的数都满足条件，奇数为必败态，偶数为必胜态。那么当爱丽丝处于k+1偶数时，爱丽丝可以选择1，这样鲍勃会处于等于k的奇数，由假定可知，奇数为必败态，那么鲍勃必败，爱丽丝必胜，也满足条件。
综上可知，我们的推论是正确的。因此只需要判断该数的奇偶，就可以直接给出结论，所以时间复杂度为$O(1)$，空间复杂度为$O(1)$。

1
2
3

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N % 2 == 0

刷题总结

博弈问题是非常有趣的编程题，其常规解法是使用动态规划，得到状态转移方程，由必胜和必败的相互状态转移，逐步求得最后结果的状态。